from typing import List


class Solution:
    def finalPrices(self, prices: List[int]) -> List[int]:
        # 找下一个更小的元素
        # 需要在栈中保存还没有找到下一个更小元素的元素下标
        # 注意while处的条件，即是否找到元素的条件，加不加=需要根据实际情况判断
        stack = []
        next_lt = [-1] * len(prices)
        for idx in range(0, len(prices)):
            while stack and prices[idx] <= prices[stack[-1]]:
                next_lt[stack.pop()] = idx
            stack.append(idx)
        print(next_lt)

        for idx, price in enumerate(prices):
            if next_lt[idx] == -1:
                continue
            prices[idx] -= prices[next_lt[idx]]
            print(prices)
        return prices
